package com.zjsru.oneDay202204;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

/**
 * @Author: likew
 * @Date: 2022/4/6
 *
 * 最小高度树
 *
 * 输入：n = 4, edges = [[1,0],[1,2],[1,3]]
 * 输出：[1]
 * 解释：如图所示，当根是标签为 1 的节点时，树的高度是 1 ，这是唯一的最小高度树。
 *
 * 输入：n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
 * 输出：[3,4]   表示根节点是3或者4都可以
 */
public class findMinHeightTrees {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if(n == 1){
            return new ArrayList<>(Arrays.asList(0));
        }
        Map<Integer, Set<Integer>> adj = getAdj(edges);
        int[] degree = getIndegree(adj);
    
        Queue<Integer> queue = new ArrayDeque<>();
        int cnt = n;
        //init queue
        for (int i = 0; i < n; i++) {
            if(degree[i] == 1){
                queue.offer(i);
            }
        }
        //BFS
        while(cnt > 2){
            int size = queue.size();
            cnt -=size;
            for (int i = 0; i < size; i++) {
               int curr = queue.poll();
                for (int next: adj.get(curr)) {
                    degree[next]--;
                    if(degree[next] == 1){
                        queue.offer(next);
                    }
                }
            }
        }
        return getAns(queue);
    }
    
    private List<Integer> getAns(Queue<Integer> queue) {
        List<Integer> list = new ArrayList<>();
        list.addAll(queue);
        return list;
    }
    
    private int[] getIndegree(Map<Integer, Set<Integer>> adj) {
        int n = adj.keySet().size();
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            ans[i] = adj.get(i).size();
        }
        return ans;
    }
    
    private Map<Integer, Set<Integer>> getAdj(int[][] edges) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int[] edge :edges) {
            map.putIfAbsent(edge[0],new HashSet<>());
            map.get(edge[0]).add(edge[1]);
            map.putIfAbsent(edge[1],new HashSet<>());
            map.get(edge[1]).add(edge[0]);
        }
        return map;
    }
    
    public static void main(String[] args) {
        findMinHeightTrees findMinHeightTrees = new findMinHeightTrees();
        int n = 1;
        int[][] edges = new int[][]{};
        System.out.println(findMinHeightTrees.findMinHeightTrees(n, edges));
    }
}
